Skip to main content

第42章 数组模拟高精度计算

在C和C++语言中，基本数据类型（如int、long long）能表示的整数范围有限，例如int型通常最大为2147483647，当需要处理超出此范围的大整数（如几百位甚至几千位的整数）时，就需要借助数组来模拟高精度计算。数组模拟高精度计算的核心思想是用数组的每个元素存储大整数的一位数字，通过模拟人工计算的方式实现加、减、乘、除等运算。

42.1 高精度计算的基本概念​

42.1.1 大整数的存储​

由于大整数的位数远超基本数据类型的表示范围，因此需要用数组来存储： 存储方式：通常将大整数的每一位数字存储在数组的一个元素中，且为了方便计算（如进位、借位），低位数字存储在数组的低位索引处（即数组下标越小，对应大整数的位越靠右）。

例如，大整数12345在数组中的存储形式为：arr[0]=5,arr[1]=4,arr[2]=3,arr[3]=2,arr[4]=1，数组长度为5（表示5位数字）。

输入与转换：大通常以字符串形式输入，需要将字符串中的每个字符转换为对应的数字后，按上述存储方式存入数组。 示例代码片段：

string s ="12345";
int arr[1000];
int len = s.size();
for (int i=0;i<len;i++){
    arr[i] = s[len-1-i]-'0';//逆序存储
}

42.1.2 高精度计算的特点​

  1. 运算规则：完全模拟人工竖式计算，包含进位（加法、乘法）、借位（减法）；
  2. 数组长度：运算结果位数可能大于原数，数组需预留多余空间；
  3. 符号处理：负数运算先处理符号，绝对值运算后再判定结果正负。

42.2 高精度加法​

42.2.1 算法步骤​

  1. 初始化结果数组，长度取两数最大位数+1，预留进位；
  2. 从数组0下标（最低位）逐位相加，累加当前数字+进位；
  3. 取模10为当前位结果，除以10更新进位；
  4. 最高位处理剩余进位；
  5. 逆序转换数组为字符串，去除前导零。

42.2.2 完整代码​

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

string add(string a, string b){
    int arrA[1000] = {0}, arrB[1000] = {0}, res[1001] = {0};
    int lenA = a.size(), lenB = b.size();
    int maxLen = max(lenA, lenB);
    // 逆序存入数组
    for (int i = 0; i < lenA; i++)
        arrA[i] = a[lenA - 1 - i] - '0';
    for (int i = 0; i < lenB; i++)
        arrB[i] = b[lenB - 1 - i] - '0';
    int carry = 0;
    for (int i = 0; i < maxLen; i++){
        int sum = arrA[i] + arrB[i] + carry;
        res[i] = sum % 10;
        carry = sum / 10;
    }
    if (carry != 0){
        res[maxLen] = carry;
        maxLen++;
    }
    // 转字符串
    string result;
    for (int i = maxLen - 1; i >= 0; i--)
        result += res[i] + '0';
    return result;
}

42.3 高精度减法​

42.3.1 算法步骤​

  1. 先比较两个大整数，保证被减数≥减数；
  2. 逆序存入数组，从最低位逐位相减；
  3. 当前位不够则向高位借1当10；
  4. 计算完成后删除结果前导零。

42.2 辅助比较函数 + 减法代码​

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

// 判断a >= b
bool greaterOrEqual(string a, string b) {
    if (a.size() != b.size())
        return a.size() > b.size();
    return a >= b;
}

string subtract(string a, string b) {
    int arrA[1000] = {0}, arrB[1000] = {0}, res[1000] = {0};
    int lenA = a.size(), lenB = b.size();
    int maxLen = lenA;
    // 逆序存储
    for (int i = 0; i < lenA; i++)
        arrA[i] = a[lenA - 1 - i] - '0';
    for (int i = 0; i < lenB; i++)
        arrB[i] = b[lenB - 1 - i];
    // 逐位借位相减
    for (int i = 0; i < maxLen; i++){
        if (arrA[i] < arrB[i]){
            arrA[i] += 10;
            arrA[i+1]--;
        }
        res[i] = arrA[i] - arrB[i];
    }
    // 去除前导零
    int resLen = maxLen;
    while (resLen > 1 && res[resLen - 1] == 0)
        resLen--;
    string result;
    for (int i = resLen - 1; i >= 0; i--)
        result += res[i] + '0';
    return result;
}

42.4 高精度乘法（大整数 × 小整数）​

42.4.1 算法步骤​

  1. 特殊判断乘数为0，直接返回"0"；
  2. 逆序存储大整数；
  3. 逐位乘小整数，累加进位；
  4. 循环处理剩余进位；
  5. 逆序生成结果字符串。

42.4.2 代码实现​

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

string multiply(string a, int b) {
    if (b == 0)
        return "0";
    int arrA[1000] = {0}, res[1000] = {0};
    int lenA = a.size();
    for (int i = 0; i < lenA; i++)
        arrA[i] = a[lenA - 1 - i] - '0';
    int carry = 0;
    int resLen = lenA;
    for (int i = 0; i < lenA; i++){
        int product = arrA[i] * b + carry;
        res[i] = product % 10;
        carry = product / 10;
    }
    // 处理剩余进位
    while (carry > 0){
        res[resLen] = carry % 10;
        carry /= 10;
        resLen++;
    }
    string result;
    for (int i = resLen - 1; i >= 0; i--)
        result += res[i] + '0';
    return result;
}

42.4.3 大整数 × 大整数思路​

两个大整数A、B逆序存入数组a[]、b[]；结果数组res[i+j] += a[i] * b[j]，全部相乘后统一处理进位。

42.5 高精度除法（大整数 ÷ 普通整数）​

42.5.1 算法步骤​

  1. 字符串逆序逻辑相反：除法从最高位开始计算；
  2. 余数初始为0，从最高位依次计算余数 * 10 + 当前数字；
  3. 商当前位 = 余数 / 除数，更新余数 = 余数 % 除数；
  4. 去除商数组前导零，输出商和最终余数。

42.5.2 代码实现​

#include <iostream>
#include <string>
#include <algorithm>
#include <utility>
using namespace std;

// 返回 pair<商字符串, 余数>
pair<string, int> divide(string a, int b) {
    int arrA[1000] = {0};
    int lenA = a.size();
    for (int i = 0; i < lenA; i++)
        arrA[i] = a[lenA - 1 - i] - '0';
    int quotient[1000] = {0};
    int remainder = 0;
    // 从最高位遍历
    for (int i = lenA - 1; i >= 0; i--){
        remainder = remainder * 10 + arrA[i];
        quotient[i] = remainder / b;
        remainder = remainder % b;
    }
    // 去掉前导零
    int qLen = lenA;
    while (qLen > 1 && quotient[qLen - 1] == 0)
        qLen--;
    string qStr;
    for (int i = qLen - 1; i >= 0; i--)
        qStr += quotient[i] + '0';
    return make_pair(qStr, remainder);
}

// 测试示例
int main(){
    auto ans = divide("12345",7);
    cout << "商：" << ans.first << "，余数：" << ans.second << endl;
    return 0;
}

42.5.3 大整数 ÷ 大整数思路​

多次高精度减法逼近商的每一位，依赖高精度减法、乘法辅助实现，代码复杂度更高。

42.6 高精度计算注意事项​

  1. 数组容量：根据题目最大位数定义数组，避免下标越界；
  2. 前导零：减法、乘法、除法运算后必须清除多余前导零，仅数字0保留单个0；
  3. 特殊值：乘数/除数为0单独特判，简化逻辑；
  4. 性能优化：超长数字可分段存储（每数组元素存4位数字）减少循环次数。